import argparse
import os
import sys
import fnmatch
import shlex

def list_top_level(source_home, exclude=[]):
    top_level_dirs_dict = {}
    top_level_files_dict = {}

    # 遍历文件
    for root, dirs, files in os.walk(source_home):

        for v in dirs[:]:
            
            vpath = os.path.join(root, v) 
            
            if not vpath.startswith(source_home + os.sep):
                print(f"错误：路径{vpath}居然不以{source_home}开头")
                sys.exit(1)
            
            vpcut = vpath[len(source_home):]
        
            # 通过glob排除文件
            for vexclude in exclude:
                if fnmatch.fnmatch(vpcut, vexclude):
                    dirs.remove(v)
                    break
        
        # 判断 root 是不是 source_home
        # 如果是，则当前目录为 source_home 下的一层目录，也就是顶级目录，也就是/
        # 如果是，就需要将 dirs 拼接 root 并添加到 top_level_dirs_dict
        # 如果不是，则忽略
        # 因为之前的排除项逻辑中，对被排除的目录执行了dirs.remove()，所以被排除的目录不会记录到顶级目录
        if root == source_home:
            for v in dirs:
                top_level_dirs_dict[os.path.join(root, v)] = 0

        for v in files:
            
            vpath = os.path.join(root, v) 
            
            if not vpath.startswith(source_home + os.sep):
                print(f"错误：路径{vpath}居然不以{source_home}开头")
                sys.exit(1)
            
            vpcut = vpath[len(source_home):]
            
            # 通过glob排除文件
            is_exclude = False
            for vexclude in exclude:
                if fnmatch.fnmatch(vpcut, vexclude):
                    is_exclude = True
                    break
            
            if is_exclude:
                continue
            
            # 判断是不是顶层目录的文件，逻辑为：
            # 判断 root 是不是 source_home
            # 如果是，那就表明是顶层目录的文件
            # 如果不是，则不进行这个处理
            # 如果是，则需要获取它的大小并将其添加到 top_level_files_dict
            # 然后，避免对它进行“寻找所属顶层目录”的逻辑
            if root == source_home:
                try:
                    size_bytes = 0
                    
                    if os.path.islink(vpath):
                        size_bytes = os.lstat(vpath).st_size
                    else:
                        size_bytes = os.path.getsize(vpath)
                    
                    top_level_files_dict[vpath] = size_bytes
                    continue
                except OSError as e:
                    print(f"无法访问 {vpath}: {e}")
                    continue

            # 判断属于哪一个顶层目录
            # 将 被判断的路径 和 顶层文件夹路径 都裁剪成以source_home为/的形式
            # ps: vpcut 存在，可复用
            # 判断 被判断的路径 以哪个 顶层文件夹路径 开始，哪个就是它的顶层文件夹
            # 增加大小
            for k, v_count in top_level_dirs_dict.items():
                
                if not k.startswith(source_home + os.sep):
                    print(f"错误：路径{k}居然不以{source_home}开头")
                    sys.exit(1)
            
                kcut = k[len(source_home):]
                
                if vpcut.startswith(kcut + os.sep):
                    try:
                        size_bytes = 0
                    
                        if os.path.islink(vpath):
                            size_bytes = os.lstat(vpath).st_size
                        else:
                            size_bytes = os.path.getsize(vpath)
                    
                        top_level_dirs_dict[k]+=size_bytes
                        break
                    except OSError as e:
                        print(f"无法访问 {vpath}: {e}")
                        break
   
    # 合并
    top_level_all_dict = top_level_dirs_dict | top_level_files_dict
    # 根据大小降序
    top_level_all_list = sorted(top_level_all_dict.items(), key=lambda x: x[1], reverse=True)

    # 转换大小、生成单位并打印
    print("源家目录下的 文件/文件夹 列表：")
    for v in top_level_all_list:
        # 单位
        unit = ""
        # 数值
        num = 0
        # 累计的bytes
        size = v[1]

        if size < 1024:
            unit, num = "B", size
        elif size < 1024**2:
            unit, num = "KB", size/1024
        elif size < 1024**3:
            unit, num = "MB", size/(1024**2)
        else:
            unit, num = "GB", size/(1024**3)

        print(f"{num:.2f} {unit} {v[0]}")

    return top_level_all_dict

def find_excluded_items(items_dict, target, max_target=1000000):
    """
    找出需要排除的项，使剩余项的总大小尽可能接近但严格小于目标值
    
    参数:
    items_dict: 字典，格式为 {项名: 大小(bytes)}
    target: 目标大小（bytes），剩余项总和必须严格小于此值
    max_target: 动态规划最大可处理的目标值（默认1,000,000）
    
    返回:
    list: 需要排除的项名列表
    """
    # 处理特殊情况：目标值<=0时排除所有项
    if target <= 0:
        return list(items_dict.keys())
    
    cap = target - 1  # 实际容量上限（严格小于target）
    keys = list(items_dict.keys())
    values = [items_dict[k] for k in keys]
    n = len(keys)
    
    # 如果目标值过大，使用贪心算法作为备选
    if cap > max_target:
        # 按大小降序排序
        sorted_items = sorted(zip(values, keys), reverse=True)
        current_sum = 0
        selected_keys = []
        for val, key in sorted_items:
            if current_sum + val <= cap:
                current_sum += val
                selected_keys.append(key)
        return [k for k in keys if k not in selected_keys]
    
    # ===== 动态规划核心算法 =====
    # 初始化DP数组和路径追踪数组
    dp = [False] * (cap + 1)
    prev = [-1] * (cap + 1)  # 记录状态转移路径
    dp[0] = True  # 空集的和为0
    
    # 动态规划填表
    for i in range(n):
        w = values[i]
        # 倒序更新避免重复选择
        for j in range(cap, w - 1, -1):
            if not dp[j] and dp[j - w]:
                dp[j] = True
                prev[j] = i  # 记录状态转移
    
    # 找到最大有效和
    max_sum = cap
    while max_sum > 0 and not dp[max_sum]:
        max_sum -= 1
    
    # 回溯找出选中的项
    selected_keys = []
    current_sum = max_sum
    while current_sum > 0:
        i = prev[current_sum]
        if i == -1:
            break  # 回溯结束
        selected_keys.append(keys[i])
        current_sum -= values[i]
    
    # 返回排除项（所有项 - 选中项）
    return [k for k in keys if k not in selected_keys]

if __name__ == "__main__":
    # 创建解析器
    parser = argparse.ArgumentParser(description='生成排除项参数')

    # 添加参数
    parser.add_argument('path', help='被扫描目录的路径（不能以/结尾）')
    parser.add_argument('size', help='剩余存储空间大小，只填数字，单位为GB')
    parser.add_argument('out_path', help='会将“被扫描目录的路径”替换为该路径（不能以/结尾）')

    # 解析参数
    args = parser.parse_args()

    if args.path[-1] == "/":
        print(f"{args.path} 不能以/结尾")       
        exit(1)

    # 如果错误会报错，如果没错误则无事发生
    int(args.size)

    if args.out_path[-1] == "/":
        print(f"{args.out_path} 不能以/结尾")
        exit(1)

    result_dict = list_top_level(args.path)

    # 排除一些目录，直到大小的总和小于args.size-5
    f_result_list = find_excluded_items(result_dict, (int(args.size)-5)*(1024**3))

    # 修改list，将 args.path 替换为 args.out_path
    new_f_result_list = []
    for v in f_result_list:
        new_f_result_list.append(args.out_path + v[len(args.path):])

    # 组成另一个脚本运行时传入的命令行参数的形式
    out_str = ""
    for v in new_f_result_list:
        out_str+=f"-e {shlex.quote(v)} "
    
    print(out_str)